package com.cuz.hot100;

import java.util.Arrays;

public class Q31nextPermutation {

    public static void main(String[] args) {
        int[] ints = {1, 3, 6, 5, 4, 3, 1};
//        int[] ints = {1,3,2};
//        int[] ints = {5, 1, 1};
//        nextPermutation1(ints);
        nextPermutation2(ints);
        System.out.println(Arrays.toString(ints));
    }

    public static void nextPermutation1(int[] nums) {
        if (nums == null || nums.length < 2) {
            return;
        }
        int len = nums.length;
        int curMax = nums[len - 1];
        boolean find = false;
        int index = len - 2;
        for (; index >= 0; index--) {
            if (nums[index] >= curMax) {
                curMax = nums[index];
            } else {
                find = true;
                break;
            }
        }
        if (find) {
            int left = index;
            int right = len;
            while (left < right - 1) {
                int mid = ((right - left) >> 1) + left;
                if (nums[mid] <= nums[index]) {
                    right--;
                } else {
                    left++;
                }
            }
            int temp = nums[index];
            nums[index] = nums[left];
            nums[left] = temp;
            Arrays.sort(nums, index + 1, len);
        } else {
            int start = 0;
            int end = len - 1;
            while (start < end) {
                int temp = nums[start];
                nums[start] = nums[end];
                nums[end] = temp;
                start++;
                end--;
            }
        }
    }

    public static void nextPermutation2(int[] nums) {
        if (nums == null || nums.length < 2) {
            return;
        }
        int index = nums.length - 2;
            //1 3 6 5 4 2 1  => index=1
        while (index >= 0 && nums[index] >= nums[index + 1]) {
            index--;
        }
        //1 3 6 5 4 2 1---> 1 4 6 5 3 2 1
        if (index>=0){
            findThenSwap(index+1,nums,index);
        }
        int end=nums.length-1;
        while (index+1<end){
            swap(nums,index+1,end);
            index++;
            end--;
        }

    }
    private static void findThenSwap(int start,int[]nums,int targetIndex){
        int left = start;
        int right = nums.length;
        while (left < right - 1) {
            int mid = ((right - left) >> 1) + left;
            if (nums[mid] <= nums[targetIndex]) {
                right--;
            } else {
                left++;
            }
        }
        swap(nums, left, targetIndex);
    }
    private static void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
}
